/*************************************************************************
	> File Name: oj-47.cpp
	> Author: Wang Bo
	> Mail: 1276106221@qq.com
	> Created Time: 2021年01月09日 星期六 14时55分04秒
 ************************************************************************/
#include <iostream>
using namespace std;
//dp[i][j] 前i件物品，背包上限位j的情况下，能装的物品最大价值
//对于dp[i][j]
//i 没选 只能从i - 1件物品组成背包价值即 dp[i - 1][j]
//i 选了 背包只能占用j - w(i)的空间dp[i][j - w[i]] + v[i];
//因此dp[i][j] 需要从上面的决策中选择最大值
//dp[i][j] = max(dp[i - 1][j] + dp[i][j - w[i]] + v[i]);

#define MAX_N 100  //物品上限
#define MAX_V 10000 //承重上限
int v[MAX_N + 5], w[MAX_V + 5];
// int dp[MAX_N + 5][MAX_V + 5];
//int dp[2][MAX_V + 5]; //滚动数组的技巧
int dp[MAX_V + 5];

int main() {
    int val, n, v, w;
    cin >> val >> n;
    // for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];
    /*
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= val; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
        }
    }
    cout << dp[n][val] << endl;
    */
    //优化 2
    /*
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= val; ++j) {
            dp[i % 2][j] = dp[(i - 1) % 2][j];
            if (j >= v[i]) dp[i % 2][j] = max(dp[i % 2][j], dp[(i - 1) % 2][j - v[i]] + w[i]);
        }
    }
    cout << dp[n % 2][val] << endl;
    */
    //优化3
    for (int i = 1; i <= n; ++i) {
        cin >> v >> w;
        for (int j = val; j >= v; --j) { /*如果从前往后更新会覆盖正确的结果*/
            if (j >= v) {
                dp[j] = max(dp[j], dp[j - v] + w);
            }
        }
    }
    return 0;
}
